<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="utf-8">
    <title>src/utils/Octree.js - cannon</title>
    <link rel="stylesheet" href="http://yui.yahooapis.com/3.9.1/build/cssgrids/cssgrids-min.css">
    <link rel="stylesheet" href="../assets/vendor/prettify/prettify-min.css">
    <link rel="stylesheet" href="../assets/css/main.css" id="site_styles">
    <link rel="icon" href="../assets/favicon.ico">
    <script src="http://yui.yahooapis.com/combo?3.9.1/build/yui/yui-min.js"></script>
</head>
<body class="yui3-skin-sam">

<div id="doc">
    <div id="hd" class="yui3-g header">
        <div class="yui3-u-3-4">
                <h1><img src="../assets/css/logo.png" title="cannon" width="117" height="52"></h1>
        </div>
        <div class="yui3-u-1-4 version">
            <em>API Docs for: 0.6.1</em>
        </div>
    </div>
    <div id="bd" class="yui3-g">

        <div class="yui3-u-1-4">
            <div id="docs-sidebar" class="sidebar apidocs">
                <div id="api-list">
                    <h2 class="off-left">APIs</h2>
                    <div id="api-tabview" class="tabview">
                        <ul class="tabs">
                            <li><a href="#api-classes">Classes</a></li>
                            <li><a href="#api-modules">Modules</a></li>
                        </ul>
                
                        <div id="api-tabview-filter">
                            <input type="search" id="api-filter" placeholder="Type to filter APIs">
                        </div>
                
                        <div id="api-tabview-panel">
                            <ul id="api-classes" class="apis classes">
                                <li><a href="../classes/AABB.html">AABB</a></li>
                                <li><a href="../classes/ArrayCollisionMatrix.html">ArrayCollisionMatrix</a></li>
                                <li><a href="../classes/Body.html">Body</a></li>
                                <li><a href="../classes/Box.html">Box</a></li>
                                <li><a href="../classes/Broadphase.html">Broadphase</a></li>
                                <li><a href="../classes/ConeEquation.html">ConeEquation</a></li>
                                <li><a href="../classes/ConeTwistConstraint.html">ConeTwistConstraint</a></li>
                                <li><a href="../classes/Constraint.html">Constraint</a></li>
                                <li><a href="../classes/ContactEquation.html">ContactEquation</a></li>
                                <li><a href="../classes/ContactMaterial.html">ContactMaterial</a></li>
                                <li><a href="../classes/ConvexPolyhedron.html">ConvexPolyhedron</a></li>
                                <li><a href="../classes/Cylinder.html">Cylinder</a></li>
                                <li><a href="../classes/Demo.html">Demo</a></li>
                                <li><a href="../classes/DistanceConstraint.html">DistanceConstraint</a></li>
                                <li><a href="../classes/Equation.html">Equation</a></li>
                                <li><a href="../classes/EventTarget.html">EventTarget</a></li>
                                <li><a href="../classes/FrictionEquation.html">FrictionEquation</a></li>
                                <li><a href="../classes/GridBroadphase.html">GridBroadphase</a></li>
                                <li><a href="../classes/GSSolver.html">GSSolver</a></li>
                                <li><a href="../classes/Heightfield.html">Heightfield</a></li>
                                <li><a href="../classes/HingeConstraint.html">HingeConstraint</a></li>
                                <li><a href="../classes/JacobianElement.html">JacobianElement</a></li>
                                <li><a href="../classes/LockConstraint.html">LockConstraint</a></li>
                                <li><a href="../classes/Mat3.html">Mat3</a></li>
                                <li><a href="../classes/Material.html">Material</a></li>
                                <li><a href="../classes/NaiveBroadphase.html">NaiveBroadphase</a></li>
                                <li><a href="../classes/Narrowphase.html">Narrowphase</a></li>
                                <li><a href="../classes/ObjectCollisionMatrix.html">ObjectCollisionMatrix</a></li>
                                <li><a href="../classes/Octree.html">Octree</a></li>
                                <li><a href="../classes/OctreeNode.html">OctreeNode</a></li>
                                <li><a href="../classes/Particle.html">Particle</a></li>
                                <li><a href="../classes/Plane.html">Plane</a></li>
                                <li><a href="../classes/PointToPointConstraint.html">PointToPointConstraint</a></li>
                                <li><a href="../classes/Pool.html">Pool</a></li>
                                <li><a href="../classes/Quaternion.html">Quaternion</a></li>
                                <li><a href="../classes/Ray.html">Ray</a></li>
                                <li><a href="../classes/RaycastResult.html">RaycastResult</a></li>
                                <li><a href="../classes/RaycastVehicle.html">RaycastVehicle</a></li>
                                <li><a href="../classes/RigidVehicle.html">RigidVehicle</a></li>
                                <li><a href="../classes/RotationalEquation.html">RotationalEquation</a></li>
                                <li><a href="../classes/RotationalMotorEquation.html">RotationalMotorEquation</a></li>
                                <li><a href="../classes/SAPBroadphase.html">SAPBroadphase</a></li>
                                <li><a href="../classes/Shape.html">Shape</a></li>
                                <li><a href="../classes/Solver.html">Solver</a></li>
                                <li><a href="../classes/Sphere.html">Sphere</a></li>
                                <li><a href="../classes/SPHSystem.html">SPHSystem</a></li>
                                <li><a href="../classes/SplitSolver.html">SplitSolver</a></li>
                                <li><a href="../classes/Spring.html">Spring</a></li>
                                <li><a href="../classes/Transform.html">Transform</a></li>
                                <li><a href="../classes/Trimesh.html">Trimesh</a></li>
                                <li><a href="../classes/TupleDictionary.html">TupleDictionary</a></li>
                                <li><a href="../classes/Vec3.html">Vec3</a></li>
                                <li><a href="../classes/Vec3Pool.html">Vec3Pool</a></li>
                                <li><a href="../classes/WheelInfo.html">WheelInfo</a></li>
                                <li><a href="../classes/World.html">World</a></li>
                            </ul>
                
                            <ul id="api-modules" class="apis modules">
                            </ul>
                        </div>
                    </div>
                </div>
            </div>
        </div>
        <div class="yui3-u-3-4">
                <div id="api-options">
                    Show:
                    <label for="api-show-inherited">
                        <input type="checkbox" id="api-show-inherited" checked>
                        Inherited
                    </label>
            
                    <label for="api-show-protected">
                        <input type="checkbox" id="api-show-protected">
                        Protected
                    </label>
            
                    <label for="api-show-private">
                        <input type="checkbox" id="api-show-private">
                        Private
                    </label>
                    <label for="api-show-deprecated">
                        <input type="checkbox" id="api-show-deprecated">
                        Deprecated
                    </label>
            
                </div>
            
            <div class="apidocs">
                <div id="docs-main">
                    <div class="content">
<h1 class="file-heading">File: src/utils/Octree.js</h1>

<div class="file">
    <pre class="code prettyprint linenums">
var AABB = require(&#x27;../collision/AABB&#x27;);
var Vec3 = require(&#x27;../math/Vec3&#x27;);

module.exports = Octree;

/**
 * @class OctreeNode
 * @param {object} [options]
 * @param {Octree} [options.root]
 * @param {AABB} [options.aabb]
 */
function OctreeNode(options){
    options = options || {};

    /**
     * The root node
     * @property {OctreeNode} root
     */
    this.root = options.root || null;

    /**
     * Boundary of this node
     * @property {AABB} aabb
     */
    this.aabb = options.aabb ? options.aabb.clone() : new AABB();

    /**
     * Contained data at the current node level.
     * @property {Array} data
     */
    this.data = [];

    /**
     * Children to this node
     * @property {Array} children
     */
    this.children = [];
}

/**
 * @class Octree
 * @param {AABB} aabb The total AABB of the tree
 * @param {object} [options]
 * @param {number} [options.maxDepth=8]
 * @extends OctreeNode
 */
function Octree(aabb, options){
    options = options || {};
    options.root = null;
    options.aabb = aabb;
    OctreeNode.call(this, options);

    /**
     * Maximum subdivision depth
     * @property {number} maxDepth
     */
    this.maxDepth = typeof(options.maxDepth) !== &#x27;undefined&#x27; ? options.maxDepth : 8;
}
Octree.prototype = new OctreeNode();

OctreeNode.prototype.reset = function(aabb, options){
    this.children.length = this.data.length = 0;
};

/**
 * Insert data into this node
 * @method insert
 * @param  {AABB} aabb
 * @param  {object} elementData
 * @return {boolean} True if successful, otherwise false
 */
OctreeNode.prototype.insert = function(aabb, elementData, level){
    var nodeData = this.data;
    level = level || 0;

    // Ignore objects that do not belong in this node
    if (!this.aabb.contains(aabb)){
        return false; // object cannot be added
    }

    var children = this.children;

    if(level &lt; (this.maxDepth || this.root.maxDepth)){
        // Subdivide if there are no children yet
        var subdivided = false;
        if (!children.length){
            this.subdivide();
            subdivided = true;
        }

        // add to whichever node will accept it
        for (var i = 0; i !== 8; i++) {
            if (children[i].insert(aabb, elementData, level + 1)){
                return true;
            }
        }

        if(subdivided){
            // No children accepted! Might as well just remove em since they contain none
            children.length = 0;
        }
    }

    // Too deep, or children didnt want it. add it in current node
    nodeData.push(elementData);

    return true;
};

var halfDiagonal = new Vec3();

/**
 * Create 8 equally sized children nodes and put them in the .children array.
 * @method subdivide
 */
OctreeNode.prototype.subdivide = function() {
    var aabb = this.aabb;
    var l = aabb.lowerBound;
    var u = aabb.upperBound;

    var children = this.children;

    children.push(
        new OctreeNode({ aabb: new AABB({ lowerBound: new Vec3(0,0,0) }) }),
        new OctreeNode({ aabb: new AABB({ lowerBound: new Vec3(1,0,0) }) }),
        new OctreeNode({ aabb: new AABB({ lowerBound: new Vec3(1,1,0) }) }),
        new OctreeNode({ aabb: new AABB({ lowerBound: new Vec3(1,1,1) }) }),
        new OctreeNode({ aabb: new AABB({ lowerBound: new Vec3(0,1,1) }) }),
        new OctreeNode({ aabb: new AABB({ lowerBound: new Vec3(0,0,1) }) }),
        new OctreeNode({ aabb: new AABB({ lowerBound: new Vec3(1,0,1) }) }),
        new OctreeNode({ aabb: new AABB({ lowerBound: new Vec3(0,1,0) }) })
    );

    u.vsub(l, halfDiagonal);
    halfDiagonal.scale(0.5, halfDiagonal);

    var root = this.root || this;

    for (var i = 0; i !== 8; i++) {
        var child = children[i];

        // Set current node as root
        child.root = root;

        // Compute bounds
        var lowerBound = child.aabb.lowerBound;
        lowerBound.x *= halfDiagonal.x;
        lowerBound.y *= halfDiagonal.y;
        lowerBound.z *= halfDiagonal.z;

        lowerBound.vadd(l, lowerBound);

        // Upper bound is always lower bound + halfDiagonal
        lowerBound.vadd(halfDiagonal, child.aabb.upperBound);
    }
};

/**
 * Get all data, potentially within an AABB
 * @method aabbQuery
 * @param  {AABB} aabb
 * @param  {array} result
 * @return {array} The &quot;result&quot; object
 */
OctreeNode.prototype.aabbQuery = function(aabb, result) {

    var nodeData = this.data;

    // abort if the range does not intersect this node
    // if (!this.aabb.overlaps(aabb)){
    //     return result;
    // }

    // Add objects at this level
    // Array.prototype.push.apply(result, nodeData);

    // Add child data
    // @todo unwrap recursion into a queue / loop, that&#x27;s faster in JS
    var children = this.children;


    // for (var i = 0, N = this.children.length; i !== N; i++) {
    //     children[i].aabbQuery(aabb, result);
    // }

    var queue = [this];
    while (queue.length) {
        var node = queue.pop();
        if (node.aabb.overlaps(aabb)){
            Array.prototype.push.apply(result, node.data);
        }
        Array.prototype.push.apply(queue, node.children);
    }

    return result;
};

var tmpAABB = new AABB();

/**
 * Get all data, potentially intersected by a ray.
 * @method rayQuery
 * @param  {Ray} ray
 * @param  {Transform} treeTransform
 * @param  {array} result
 * @return {array} The &quot;result&quot; object
 */
OctreeNode.prototype.rayQuery = function(ray, treeTransform, result) {

    // Use aabb query for now.
    // @todo implement real ray query which needs less lookups
    ray.getAABB(tmpAABB);
    tmpAABB.toLocalFrame(treeTransform, tmpAABB);
    this.aabbQuery(tmpAABB, result);

    return result;
};

/**
 * @method removeEmptyNodes
 */
OctreeNode.prototype.removeEmptyNodes = function() {
    var queue = [this];
    while (queue.length) {
        var node = queue.pop();
        for (var i = node.children.length - 1; i &gt;= 0; i--) {
            if(!node.children[i].data.length){
                node.children.splice(i, 1);
            }
        }
        Array.prototype.push.apply(queue, node.children);
    }
};

    </pre>
</div>
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>
<script src="../assets/vendor/prettify/prettify-min.js"></script>
<script>prettyPrint();</script>
<script src="../assets/js/yui-prettify.js"></script>
<script src="../assets/../api.js"></script>
<script src="../assets/js/api-filter.js"></script>
<script src="../assets/js/api-list.js"></script>
<script src="../assets/js/api-search.js"></script>
<script src="../assets/js/apidocs.js"></script>
</body>
</html>
